package cxydmmszl.chapter05.t086;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * 删除多余的字符得到字典序最小的字符串
 * <li style="color: green;">Desc</li>
 * 给一个全是小写字母的字符串 str，删除多余字符，使得每种字符只保留一个，
 * 并且让最终结果字符串字典序最小。
 * <li style="color: green;">Input</li>
 * 输入包含一行字符串，代表 str（1<=length(str)<=10^5）
 * <li style="color: green;">Output</li>
 * 输出一行，代表删除后的字符串。
 * <li style="color: blue;">Link</li> CD121
 *
 * @author habitplus
 * @since 2021-09-09 20:26
 */
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        br.close();

        s = removeDuplicateLetters1(s);

        System.out.println(s);
    }

    private static String removeDuplicateLetters2(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        StringBuilder sb = new StringBuilder();

        char[] chs = s.toCharArray();
        int n = chs.length;
        int idx;
        // 建立 hash table，存储每个字符最后出现的位置
        // 位置从 1 开始，0 表示已经去除该字符，或者没有出现该字符
        int[] lastIndex = new int[26];
        int[] firstIndex = new int[26];

        for (int i = 0; i < n; i++) {
            idx = chs[i] - 'a';
            lastIndex[idx] = i + 1;
            if (firstIndex[idx] == 0) {
                firstIndex[idx] = i + 1;
            }
        }

        int i = 0;
        int minKey;
        while (i < n) {
            idx = chs[i] - 'a';
            if (lastIndex[idx] == 0 || lastIndex[idx] != i + 1) {
                // 已经去除的字符，或者当前字符后续还会出现
                i++;
                continue;
            }

            // 当前位置是该字符出现的最后位置
            // 寻找当前位置左边的最小字符
            minKey = idx;
            for (int j = 0; j < lastIndex.length; j++) {
                if (firstIndex[j] > 0 && i >= firstIndex[j] - 1 && minKey > j) {
                    minKey = j;
                }
            }

            // 找到了一个字符
            sb.append((char) ('a' + minKey));
            // 排除 minChar
            // 0 表示该字符已经加入结果集，应该排除该字符了
            lastIndex[minKey] = 0;
            firstIndex[minKey] = 0;
        }

        return sb.toString();
    }

    private static String removeDuplicateLetters1(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }

        StringBuilder sb = new StringBuilder();

        char[] chs = s.toCharArray();
        // 建立 hash table，记录每个字符出现的次数
        int[] fre = new int[26];

        for (char c : chs) {
            fre[c - 'a']++;
        }

        int idx;
        int i = 0;
        int l = 0;
        while (i < chs.length) {
            idx = chs[i] - 'a';
            if (fre[idx] == -1 || fre[chs[i] - 'a'] > 1) {
                // 已经取过的字符，或者当前字符的频数大于 1
                fre[idx] = fre[idx] == -1 ? fre[idx] : fre[idx] - 1;
                i++;
                continue;
            }
            // 当前字符已经是该字符出现的最后位置，即 fre[idx] = 1
            // 寻找 idx 左边的最小字符的下标
            int k = i;
            for (int j = l; j < i; j++) {
                if (fre[chs[j] - 'a'] != -1 && chs[k] > chs[j]) {
                    k = j;
                }
            }

            // 找到了一个字符
            sb.append(chs[k]);
            // 排除 minChar
            fre[chs[k] - 'a'] = -1;
            l = k + 1;
        }

        return sb.toString();
    }
}
